package acwing.dfs;

import java.util.Scanner;

/**
 * 全排列
 *
 * @author yang
 * @date 2021/11/28
 */
public class 全排列 {

    static Scanner sc = new Scanner(System.in);
    static int n = sc.nextInt();
    static int N = n + 1;
    static int[] path = new int[N];
    static boolean[] st = new boolean[N];

    public static void main(String[] args) {

        dfs(0);
    }

    public static void dfs(int u) {
        if (u == n) {
            for (int i = 0; i < n; i++) System.out.print(path[i]);
            System.out.println();
            return;
        }
        for (int i = 1; i <= n; i++) {
            if (!st[i]) {
                path[u] = i;
                st[i] = true;
                dfs(u + 1);
                st[i] = false;
            }
        }
    }

}
